package com.lw.leetcode.bingChaJi.b;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1319. 连通网络的操作次数
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/31 13:51
 */
public class MakeConnected {

    public static void main(String[] args) {
        MakeConnected test = new MakeConnected();

        // 1
        int n = 4;
        int[][] arr = {{0, 1}, {0, 2}, {1, 2}};

        // 2
//        int n = 6;
//        int[][] arr = {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}};

        // -1
//        int n = 6;
//        int[][] arr = {{0, 1}, {0, 2}, {0, 3}, {1, 2}};

        // 0
//        int n = 5;
//        int[][] arr = {{0, 1}, {0, 2}, {3, 4}, {2, 3}};

        // 0
//        int n = 10;
//        int[][] arr = {{6, 8}, {0, 4}, {1, 2}, {5, 8}, {0, 9}, {1, 8}, {1, 4}, {4, 9}, {4, 6}, {3, 7}, {2, 4}, {3, 5}, {6, 7}, {4, 5}};


        int i = test.makeConnected(n, arr);
        System.out.println(i);
    }

    public int makeConnected(int n, int[][] connections) {
        int length = connections.length;
        if (n - 1 > length) {
            return -1;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] arr : connections) {
            int a = arr[0];
            int b = arr[1];
            int x = find(a, map);
            int y = find(b, map);
            int min = Math.min(x, y);
            if (x != y) {
                map.put(Math.max(x, y), min);
            }
        }
        int count = -1;
        for (int i = 0; i < n; i++) {
            if (map.get(i) == null) {
                count++;
            }
        }
        return count;
    }

    private int find(int k, Map<Integer, Integer> map) {
        Integer v = map.get(k);
        if (v == null) {
            return k;
        }
        int i = find(v, map);
        if (i != k) {
            map.put(k, i);
        }
        return i;
    }

}
